package com.zklh.leetcode.interviewTop150;

import java.util.ArrayList;
import java.util.List;

/**
 * 文本左右对齐算法实现
 * author: tongnan
 * date: 2024/8/2
 */
public class Solution68 {
    public List<String> fullJustify(String[] words, int maxWidth) {
        int current = 0;
        List<String> result = new ArrayList<>();
        while (current < words.length) {
            int lineCharWidth = words[current].length();
            int lineStart = current;
            int lineEnd = current+1;
            while (lineEnd < words.length && lineCharWidth + words[lineEnd].length() + (lineEnd - lineStart) <= maxWidth) {
                lineCharWidth += words[lineEnd].length();
                lineEnd ++;
            }
            // 最后一行左对齐
            if (isLastLine(words, lineEnd)) {
                result.add(generateLeftJustifyLine(words, maxWidth, lineStart, lineEnd));
            } else { // 其余行 中间对齐
                result.add(generateMiddleJustifyLine(words, maxWidth, lineStart, lineCharWidth, lineEnd));
            }
            current = lineEnd;
        }
        return result;
    }

    private static boolean isLastLine(String[] words, int lineEnd) {
        return lineEnd >= words.length;
    }

    private String generateMiddleJustifyLine(String[] words, int maxWidth, int lineStart, int lineCharWidth, int lineEnd) {
        String line = "";
        int lineCurrent = lineStart;
        int avgSpaceNum = (maxWidth - lineCharWidth) / Math.max(1, lineEnd - lineStart - 1);
        int residueSpaceNum = (maxWidth - lineCharWidth) % Math.max(1, lineEnd - lineStart - 1);
        if (lineEnd - lineStart == 1) {
            line = words[lineCurrent] + generateSpace(avgSpaceNum + residueSpaceNum);
        } else {
            StringBuilder sb = new StringBuilder();
            while (lineCurrent < lineEnd - 1) {
                sb.append(words[lineCurrent]).append(generateSpace(avgSpaceNum + (residueSpaceNum > 0 ? 1 : 0)));
                residueSpaceNum--;
                lineCurrent++;
            }
            sb.append(words[lineCurrent]);
            line = sb.toString();
        }
        return line;
    }

    private String generateLeftJustifyLine(String[] words, int maxWidth, int lineStart, int lineEnd) {
        int lineCurrent = lineStart;
        StringBuilder sb = new StringBuilder();
        while (lineCurrent < lineEnd - 1) {
            sb.append(words[lineCurrent]).append(generateSpace(1));
            lineCurrent++;
        }
        sb.append(words[lineCurrent]).append(generateSpace(maxWidth - sb.length()));
        String line = sb.toString();
        return line;
    }

    private String generateSpace(int num) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < num; i++) {
            sb.append(" ");
        }
        return sb.toString();
    }

    public static void main(String[] args) {
        Solution68 solution68 = new Solution68();
        String[] words = {"What","must","be","acknowledgment","shall","be"};
        int maxWidth = 16;
        List<String> strings = solution68.fullJustify(words, maxWidth);
        System.out.println(strings);
    }
}
